package solution.tree;

import common.TreeNode;
import common.util.TreeNodeUtil;

/**
 * @author : wenchao.long
 * @date : Created in 2021/7/13 13:47 周二
 * @description : 二叉搜索树的最近公共祖先
 */
public class LowestCommonAncestorSolution {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root.val < p.val && root.val > q.val) {
            return root;
        }
        if (root.val > p.val && root.val < q.val) {
            return root;
        }
        if (root.val == p.val) {
            return p;
        }
        if (root.val == q.val) {
            return q;
        }
        if (root.val < p.val && root.val < q.val) {
            return lowestCommonAncestor(root.right, p, q);
        }
        return lowestCommonAncestor(root.left, p, q);
    }

    public static void main(String[] args) {
        TreeNode root = TreeNodeUtil.create(6, 2, 8, 0, 4, 7, 9, null, null, 3, 5);
        TreeNodeUtil.levelOrderList(root);

        TreeNode node = new LowestCommonAncestorSolution().lowestCommonAncestor(root, new TreeNode(0), new TreeNode(4));
        assert node != null;
        System.out.println(node.val);
    }

}
